# -*- coding: utf-8 -*-
"""
Created on Thu Nov 15 23:30:52 2018

@author: Administrator
"""

class CircleSeqQueue:
    """循环顺序队列
    创建循环顺序队列，队列可自动扩充
    """
    def __init__(self, init_size = 8):
        """初始化
        elements:元素存储
        head: 表头元素位置
        rear: 表尾元素位置
        size: 表的大小
        length: 表的长度
        """
        self.elements = []
        self.head = -1
        self.rear = 0
        self.size = init_size
        self.length = 0

    def is_empty(self):
        if self.length == 0:
            return True
        return False
    
    def queue_length(self):
        return self.length
    
    def enqueue(self, element):
        # 如果队空
        if self.is_empty():
            self.elements.append(element)
            self.head += 1
            self.rear += 1
            self.length += 1
            return
        # 如果有元素
        # 队满，自动扩展队列
        if (self.rear + 1) % self.size == self.head:
            self.__auto_extend()
        # 队不满，入队
        self.elements.append(element)
        self.rear = (self.rear + 1) % self.size
        self.length += 1
    
    
    def __auto_extend(self):
        new_list = []
        # 如果队满，自动扩展队列
        if (self.rear + 1) % self.size == self.head:
            p = self.head
            while p != self.rear:
                temp = self.elements[p]
                new_list.append(temp)
                p = (p + 1) % self.size
        # 自动扩展后，更新新队列状态信息
        self.elements = new_list
        self.head = 0
        self.rear = self.length
        self.size *= 2
        
    def dequeue(self):
        if self.is_empty():
            raise ValueError("circle queue is empty!")
        result = self.elements[self.head]
        self.head = (self.head + 1) % self.size
        return result
    
    def print_all(self):
        result = []
        # 如果没有元素
        if self.length == 0:
            return result
        else:
            p = self.head
            while p != self.rear:
                result.append(self.elements[p])
                p = (p + 1) % self.size
        return result